package jzoffer;

import java.util.*;

/**
 * @author MaoLin Wang
 * @date 2020/10/19 5:47 下午
 */
public class _43把数组排成最小的数 {
    public String minNumber(int[] nums) {
        List<String>treeSet=new ArrayList<>();
        for (int num : nums) {
            treeSet.add(num+"");
        }
        Collections.sort(treeSet, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String n12=o1+o2;
                String n21=o2+o1;

                return n12.compareTo(n21);
            }
        });
        StringBuilder sb=new StringBuilder();
        while (!treeSet.isEmpty()){
            sb.append(treeSet.remove(0));
        }
        return sb.toString();
    }
    public String minNumber2(int[] nums) {
        quickSort(nums,0,nums.length-1);
        StringBuilder sb=new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    private void quickSort(int[] nums,int left,int right) {
        if (left<right){
            int mid=partition(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int l=left;
        int r=right+1;
        int pivot=nums[left];

        while (true){
            int res;
            while ((res=(nums[++l]+""+pivot).compareTo(pivot+""+nums[l]))<0){
                if (l>=right){
                    break;
                }
            }
            while ((res=(nums[--r]+""+pivot).compareTo(pivot+""+nums[r]))>0){
                if (r<=left){
                    break;
                }
            }
            if (l>=r){
                break;
            }
            swap(nums,l,r);

        }
        swap(nums,r,left);
        return r;
    }

    private void swap(int[] nums, int l, int r) {
        int temp=nums[l];
        nums[l]=nums[r];
        nums[r]=temp;
    }

    public static void main(String[] args) {
        String s = new _43把数组排成最小的数().minNumber2(new int[]{3, 30, 34, 5, 9});
        System.out.println(s);
    }
}
